#include <iostream>
#include <random>
#include <vector>

void shellSort(std::vector<int>& arr)
{
    int d=arr.size();
    while(d>1)
    {
        d/=2;
        for(int x=0;x<d;x++)
        {
            for(int i=x+d;i<arr.size();i+=d)
            {
                int temp=arr.at(i);
                int j={};
                for(j=i-d;(j>=0) && (arr.at(j)>temp);j-=d)
                    arr.at(j+d)=arr.at(j);
                arr.at(j+d)=temp;
            }
        }
    }
}

int main()
{
    std::uniform_int_distribution<int> randomInt(1,1000);
    std::default_random_engine randomE;
    std::vector<int> arr;
    arr.resize(50);
    for(int& i:arr)
        i=randomInt(randomE);
    shellSort(arr);
    for(int i:arr)
        std::cout<<i<<' ';
    std::cout<<std::endl;
    return 0;
}